﻿namespace Leetcode.N0632;

public class Solution
{
    public int[] SmallestRange(IList<IList<int>> nums)
    {
        var queue = new PriorityQueue<(int val, int index1, int index2), int>();
        var max = 0;
        for (int i = 0; i < nums.Count; i++)
        {
            queue.Enqueue((nums[i][0], i, 0), nums[i][0]);
            max = Math.Max(max, nums[i][0]);
        }

        var left = queue.Peek().val;
        var right = max;

        while (true)
        {
            var item = queue.Dequeue();

            if (item.index2 == nums[item.index1].Count - 1)
            {
                break;
            }
            
            var val = nums[item.index1][item.index2 + 1];
            queue.Enqueue((val, item.index1, item.index2 + 1), val);
            max = Math.Max(max, val);
            if (max - queue.Peek().val < right - left)
            {
                left = queue.Peek().val;
                right = max;
            }
        }

        return new[] { left, right };
    }
}